#pragma ident "$Id: Kruskal.cpp 2596 2011-12-19 11:22:04Z shjzhang $"

/**
 * @file Kruskal.cpp
 * Class to find the edges of the minimal spanning tree of the 'observed' network.
 * using Kruskal algorithm.
 */


#include "Kruskal.hpp"

namespace gpstk
{
     
   using namespace std;


      // Creating the minimum spanning trees from the edges of the network.
   EdgeSet Kruskal::createMST() 
   {
         // Temporary edges set
      EdgeSet indepEdges;

         // Make the component from current edges
      makeComponent(currentEdges);

         // Clear the indepEdges again
      indepEdges.clear();

         // Choose the 'light' edges from the 'currentEdges'
      indepEdges = chooseEdges(currentEdges);

      currentIndepEdges = indepEdges;

         // Return the independent edges
      return currentIndepEdges;

   }  // End of "void createMininumSpanningTree()"



      /** Make the component for the vertex in the observation graph.
       *
       * @param vertex       vertex 
       */
   void Kruskal::makeComponent(const EdgeSet& edgeSet) 
   {

         // Firstly, extract the vertex from current edges 
      for( EdgeSet::const_iterator it = edgeSet.begin();
           it != edgeSet.end();
           ++it )
      {
            // Get source vertex from Edge and insert Vertex into vertexSet
         Vertex vSource = (*it).getSource();

            // Insert the 'source' into vertexSet
         vertexSet.insert( vSource );

            // Get satellite vertex from Edge and insert Vertex into vertexSet
         Vertex vSat = (*it).getSatellite();

            // Insert the 'source' into vertexSet
         vertexSet.insert( vSat );

      }  // End of 'for( EdgeSet:: const_iterator it = ....'
      

         // Secondly, Set the component value
      int c(1);
      for( VertexSet::const_iterator it = vertexSet.begin();
           it != vertexSet.end();
           ++it )
      {
            // The component of this vertex is 'c'
         vtxCMPValueMap[*it] = c;
          
            // Component increment
         c++;
      }

   }  // End of method 'makeComponent()'



      /* Choose the MST edges from current edges
       *
       * @param edgeSet       Vertex of the graph 
       */
   EdgeSet Kruskal::chooseEdges(const EdgeSet& edgeSet)
   {
         // Independent edge set
      EdgeSet indepEdges;

         // Component number for source
      int cmpSource;

         // Component number for satellite
      int cmpSat;

         // Loop the 'edgeSet' to create independent edges
      for( EdgeSet::const_iterator it = edgeSet.begin();
           it != edgeSet.end();
           ++it )
      {
            // Get SourceID from Edge
         Vertex vSource = (*it).getSource();

            // Get SatID from Edge
         Vertex vSat = (*it).getSatellite();

            // Source Vertex component 
         cmpSource = findComponent( vSource ); 

            // Satellite Vertex component 
         cmpSat    = findComponent( vSat ); 

            // Merge the vertex into the same set 
         if( cmpSource != cmpSat)
         {
               // Add this edge into current independent edges 
            indepEdges.insert(*it);

               // Merge the component of source and satellite vertex
            mergeComponents(vSource, vSat);

         } // End of 'if ( cmpSource != comSat )'

      }  // End of 'for ( EdgeSet::const_iterator it = ...'

  
      // now, let's print out the component for independent edges
      std::set<int> cmpSet;
      std::map<int, int> cmpSizeMap;
      for( EdgeSet::const_iterator it =indepEdges.begin();
           it != indepEdges.end();
           ++it )
      {
             // Get SourceID from Edge
          Vertex vSource = (*it).getSource();
             // Source Vertex component 
          cmpSource = findComponent( vSource ); 

          cmpSet.insert(cmpSource);
          if( cmpSizeMap.find(cmpSource) != cmpSizeMap.end() )
          {
              cmpSizeMap[cmpSource] ++;
          }
          else
          {
              cmpSizeMap[cmpSource] = 1;
          }

      }

      int maxCmpValue(0);
      int maxSize(0);
      for(std::map<int, int>::iterator cmpIt=cmpSizeMap.begin();
              cmpIt!=cmpSizeMap.end();
              cmpIt++)
      {
          if( (*cmpIt).second > maxSize )
          {
              maxSize = (*cmpIt).second;
              maxCmpValue = (*cmpIt).first;
          }
      }

      // now, let's print out the component for independent edges
      EdgeSet tempIndepEdges;
      SourceIDSet tempSourceSet;
      SatIDSet tempSatSet;
      for( EdgeSet::const_iterator it =indepEdges.begin();
           it != indepEdges.end();
           ++it )
      {
             // Get SourceID from Edge
          Vertex vSource = (*it).getSource();
             // Source Vertex component 
          cmpSource = findComponent( vSource ); 
          if(cmpSource==maxCmpValue)
          {
              tempIndepEdges.insert((*it));
              tempSourceSet.insert((*it).getSource());
              tempSatSet.insert((*it).getSatellite());
          }
      }

      // only return the connected independent edges with maximum vertexs
      indepEdges = tempIndepEdges;

      connectedSourceSet = tempSourceSet;
      connectedSatSet = tempSatSet;

      // warning
      // you MUST make sure independent edges belongs to 
      // the same graph by judging the compoment of the vertexs

         // Return the independent edges
      return indepEdges;

   } // End of method "Kruskal::chooseEdges()"



      /** find the component number of the given vertex.
       *
       * @param vertex       vertex 
       */
   int Kruskal::findComponent(const Vertex& vertex) 
   {

         // Component value
      int component ;

         // The iterator for the 'vStart' and 'vEnd'
      VertexValueMap::iterator it = vtxCMPValueMap.find(vertex);

         // If found, return 
      if( it != vtxCMPValueMap.end() )
      {
         component = (*it).second;
      }

         // Returen 
      return component;

   }  // End of 'findComponent( )'



      /* Merge the component of the source vertex and satellite vertex 
       * if the component for each other is differenet 
       *
       * @param vSource      Source Vertex of the graph 
       * @param vSat         Satellite Vertex of the graph
       *
       */
   void Kruskal::mergeComponents(const Vertex& vSource,
                                 const Vertex& vSat) 
   {
         // Get the component value of the vSource
      int cmpSource( findComponent( vSource) ) ;

         // Get the component value of the vSource
      int cmpSat( findComponent( vSat)) ;

         // Change the component of the source and satellite vertex
      if( cmpSource < cmpSat )
      {
            // Set all the vertex' components, which equals 
            // 'cmpSat',  to 'cmpSource'
         for( VertexSet::iterator itVtx = vertexSet.begin();
              itVtx != vertexSet.end();
              ++itVtx )
         {
            if(vtxCMPValueMap[*itVtx] == cmpSat)
            {
               vtxCMPValueMap[*itVtx] =  cmpSource;
            }
         }

      }
      else
      {
            // Set all the vertex' components, which equal with 
            // 'cmpSource', to 'cmpSat'
         for( VertexSet::iterator itVtx = vertexSet.begin();
              itVtx != vertexSet.end();
              ++itVtx )
         {
            if(vtxCMPValueMap[*itVtx] == cmpSource)
            {
               vtxCMPValueMap[*itVtx] =  cmpSat;
            }
         }

      }  // End of 'if( cmpSource < cmpSat )' 

   }  // End of method "Kruskal::mergeComponents()"


}  // End of namespace gpstk
